from collections import defaultdict
from typing import List


class Trie:
    def __init__(self):
        self.children = defaultdict(Trie)
        self.word = ""
        self.is_word = False

    def insert(self, word):
        cur = self
        for c in word:
            cur = cur.children[c]
        cur.is_word = True
        cur.word = word

    # def remove(self, word):
    #     stack = [(self, "")]
    #     for c in word:
    #         stack.append((stack[-1].children[c], c))
    #     stack[-1][0].is_word = False
    #     while len(stack) > 1 and len(stack[-1][0].children) == 0 and stack[-1][0].is_word is False:
    #         cur, c = stack.pop()
    #         stack[-1][0].children.pop(c)


class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trie = Trie()
        for word in words:
            trie.insert(word)

        # 深度优先搜索
        def dfs(now, i1, j1):
            if now.is_word:
                ans.add(now.word)

            ch = board[i1][j1]
            board[i1][j1] = "#"
            for i2, j2 in [(i1 + 1, j1), (i1 - 1, j1), (i1, j1 + 1), (i1, j1 - 1)]:
                if 0 <= i2 < m and 0 <= j2 < n:
                    if board[i2][j2] in now.children:
                        dfs(now.children[ch], i2, j2)
            board[i1][j1] = ch

        ans = set()
        m, n = len(board), len(board[0])

        # 遍历二维网格
        for i in range(m):
            for j in range(n):
                if board[i][j] in trie.children:
                    dfs(trie.children[board[i][j]], i, j)

        return list(ans)


if __name__ == "__main__":
    # ["eat","oath"]
    print(Solution().findWords(
        board=[["o", "a", "a", "n"], ["e", "t", "a", "e"], ["i", "h", "k", "r"], ["i", "f", "l", "v"]],
        words=["oath", "pea", "eat", "rain"]))

    # []
    print(Solution().findWords(board=[["a", "b"], ["c", "d"]], words=["abcb"]))

    # ["a"]
    print(Solution().findWords(board=[["a"]], words=["a"]))

    # []
    print(Solution().findWords(board=[["a", "a"]], words=["aaa"]))
